\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 4}

\paragraph{Задание 1.} Числами Белла $B\left(n\right)$ называются числа, равные количеству всевозможных разбиений множества из $n$ элементов. Очевидно, что:
\[
	B\left(n\right) = \sum_{k=0}^{n} S\left(n,k\right)
\]
Доказать а) некомбинаторно; б) комбинаторно следующее рекуррентное соотношение для чисел Белла:
\[
	\begin{split}
		& B\left(n+1\right) = \sum_{i=0}^{n} \binom{n}{i} B\left(i\right) \\
		& B\left(0\right) = 1
	\end{split}
\]

\begin{Proof}
Сначала рассмотрим вспомогательное утверждение:
\begin{equation}
	S\left(n,k\right) = \sum_{i=k-1}^{n-1} \binom{n-1}{i} S\left(i, k-1\right)
	\label{math::recurrent}
\end{equation}

Докажем это утверждение. Рассматриваем множество всех разбиений некоторого множества $X$. Выделем в множестве $X$ элемент $a$. Для каждого $M \subseteq X$ такого что $a \in M$ и $\left|M\right|=i$, существует $S\left(n-i,k-1\right)$ разбиений $X$ на $k$ блоков, таких что $M$ является одним из блоков. А выбрать такое множество $M$ можно $\binom{n-1}{i-1}$ способами, тогда:
\[
\begin{split}
	& S\left(n,k\right) = \sum_{i=1}^{n-k+1} \binom{n-1}{i-1}S\left(n-i,k-1\right) = \sum_{i=1}^{n-\left(k-1\right)} \binom{n-1}{n-i}S\left(n-i,k-1\right) = \\
& = \sum_{\tilde i=k-1}^{n-1} \binom{n-1}{\tilde i} S\left(\tilde i,k-1\right)
\end{split}
\]

Далее рассмотрим утверждение, которое необходимо доказать:
\[
	\begin{split}
	& B\left(n+1\right) = \sum_{i=0}^n \binom{n}{i} B\left(i\right) = \sum_{i=0}^n \binom{n}{i} \sum_{k=0}^i S\left(i,k\right) = \\
	& = \sum_{i=0}^n \binom{n}{i} \sum_{k=0}^{i+1} S\left(i,k-1\right) = \sum_{i=-1}^n \sum_{k=0}^{i+1} \binom{n}{i} S\left(i,k-1\right) = \\
	& = \sum_{k=0}^{n+1} \sum_{i=k-1}^{n} \binom{n}{i} S\left(i,k-1\right) = \sum_{k=0}^{n+1} S \left(n+1,k\right)
	\end{split}
\]
последнее преобразование производилось по формуле \ref{math::recurrent}

Рекуррентное доказательство гораздо проще. Пусть есть множество $X = \{1,2,...,n,n+1\}$. Будем рассматривать множество его разбиений. Зафиксируем элемент $n+1$ этот элемент входит в подмножество $M \subseteq X$, где $\left|M\right|=i+1$, выбрать такое подмножество можно $\binom{n}{n-i} = \binom{n}{k}$ способами (один элемент зафиксирован, остальные выбираем из $n$ возможных). Способов разбить все множесто $X$ так чтобы каждое разбиение содержало $M$ в качестве блока разбиения $B\left(n-i=k\right)$ (т. е. разбиваем множество $X \setminus M$), суммируем по всем $k$:
\[
	B\left(n+1\right)=\sum_{k=0}^n \binom{n}{k} B\left(k\right)
\]
\end{Proof}

\paragraph{Задание 2.} Доказать, что равенства
\[
	k^n=\sum_{i=1}^n \binom{k}{i} \hat S \left(n,i\right) = \sum_{i=1}^k \binom{k}{i} \hat S \left(n,i\right)
\]
выражающие количество всех отображений из $n$-множества $X$ в $k$-множество $Y$ через биномиальные коэффициенты и числа $\hat S \left(n,k\right)$, верны для любых неотрицательных значений $n$ и $k$ (т.е. при $n<k$, и при $n\ge k$ эти равенства остаются верными как при суммировании по $i$ от 0 до $n$, так и при суммировании от 0 до $k$).

\begin{Proof}
Сначала рассмотрим равенство:
\[
	k^n = \sum_{i=1}^k \binom{k}{i} \hat S \left(n,i\right)
\]
Рассмотрим случай $k>n$. $\hat S \left(n,k\right) = 0$ при $k>n$, следовательно можно без последствий суммировать не до $k$, а до $n$ (эквивалентно добавлению нулевых слагаемых в сумму), т. е. получаем:
\[
	k^n = \sum_{i=1}^k \binom{k}{i} \hat S \left(n,i\right) = \sum_{i=1}^n \binom{k}{i} \hat S \left(n,i\right)
\]
Для случая $k < n$ начиная с $i > k$ получается, что $\binom{k}{i} = 0$, следовательно мы также можем суммировать до $n$ (опять же эквивалентно добавлению нулевых слагаемых):
\[
	k^n = \sum_{i=1}^k \binom{k}{i} \hat S \left(n,i\right) = \sum_{i=1}^n \binom{k}{i} \hat S \left(n,i\right)
\]
т. е. обе формулы эквивалентны как при $k>n$ так и при $k<n$, при $k=n$ эквиалентность формул очевидна.
\end{Proof}

\paragraph{Задание 3.} Как следствие, доказать, что для любых целых $k$ справедлива формула:
\[
	k^n = /sum_{i=0}^n \left(k\right)_i S \left(n,i\right)
\]
Доказать, что она остается верной для любых вещественных $x \in \mathbb{R}$:
\[
	x^n = \sum_{i=0}^n \left(x\right)_i S \left(n,i\right)
\]
\begin{Proof}
Покажем первое утверждение:
\[
	k^n = \sum_{i=0}^n \binom{k}{i} \hat S \left(n,i\right) = \sum_{i=0}^n \left(i!\right) \frac{\left(k\right)_i}{i!} S \left(n,i\right)
\]
откуда получаем требуемое выражение. Второе утерждение доказывается очевидно. Пусть $S \left(n,k\right)$ - число, а $\left(k\right)_i$ - многочлен от переменной $k$ степени $i$, т. е. их сумма есть многочлен степени $n$, и в левой части также стоит многочлен степени $n$, оба многочлена свопадают для всех натуральных значений $k$, а значит и для произвольных вещественных значений $k$ они также совпадают.
\end{Proof}

\paragraph{Задание 4.} Показать, что количество размещений $n$ различимых предметов по $k$ неразличимым ящикам при отсутствии ограничений на количество предметов  одном ящике равно:
\[
	B\left(n,k\right) := S\left(n,1\right) + S\left(n,2\right) + ... + S \left(n,k\right)
\]
\begin{Proof}
Так как все ящики одинаковы, нам важно только каким образом мы можем сгруппировать $n$ предметов, и не важно в какой ящик каждая группа попадет. Так как нет ограничений на количество предметов в одном ящике, т. е. $n \ge a_i \ge 0$, где $a_i$ - количество предметов в $i$-ом ящике, то нас интересуют все возможные разбиения $n$-множества на $i$ блоков, где $k \ge i > 0$, количество неупорядоченных разбиений $n$-множества на $i$ блоков $S\left(n,i\right)$, просуммировав по всем возможным количествам блоков (по всем $i$):
\[
	\sum_{i=1}^{k} \left(n,i\right)
\]
\end{Proof}

\paragraph{Задание 5.} Показать, что количество размещений $n$ различимых предметов по $k$ неразличимым ящикам при условии, что в одном ящике может распологаться не более одного предмета, равно 1, если $n \le k$, и 0, если $n > k$

\begin{Proof}
Рассмотрим, сначала простой случай, когда $n>k$, т. е. когда количество предметов строго большо количества ящиков, таким образом, если мы разложим в каждый ящик по 1 предмету, то неразложенными остануться еще $n-k > 0$ предметов, следовательно необходимого размещения не существует.

Теперь рассмотрим случай, когда $n \le k$. Этот случай сложнее, но не на много. Во-первых, так как ящики не различимы, то существует только один способ выбрать $n$ из них (т. е. любые способы выбора $n$ ящиков не отличимы друг от друга). Далее каждому из ящиков сопоставлется один предмет, число способов выбрать $n$-последовательность из $n$-разлчиных предметов равно $n!$, но так как все выбранные ящики идентичны, то необходимо поделить $n!$ на количество всевозможных перестановок $n$ ящиков, т. е. на $n!$, в итоге получаем 1.
\end{Proof}
\end{document}
